Many applications in the field of computer graphics require animation of soft bodies, i.e. deformable objects such as cloth, vegetation, hair, muscles, etc. Examples of such applications include video games, computer-aided design, and education tools like surgical simulators. Soft-body animation typically involves solving a large set of equations governing the dynamics of the object to be animated, and an increasing number of applications requires the dynamical equations to be solved extremely fast.
A case in point of an application with particularly severe speed requirements is interactive animation in real time, such as when a video game player moves an object across the screen using a computer mouse, or a finger if the screen is a touch screen. In order to achieve high quality interactivity at 30 frames per second the total amount of time available to update all the components of a scene is 33 milliseconds, and only a fraction of this time can be devoted to advancing the dynamics of the animated objects. Often, the available time slice for physically-based animations is as little as 5 milliseconds. The accuracy of the solution of linear iterative solvers depends on the number of iterations; however only a small number of iterations can be accommodated in such a tight time budget. Traditionally, this has typically forced the use of simple objects composed from few constraints whose dynamics can be solved in few iteration steps, something which may reduce animation quality.
The dynamical equations are usually solved using linear iterative techniques, two popular examples being the Gauss-Seidel method and the Jacobi method. However, such methods often fail to make optimal use of parallelism, which is becoming an increasingly important technique for speeding up computations. The Gauss-Seidel method, for example, is very difficult to implement on parallel computing architectures. Parallel implementation of the Jacobi method is easier, but due to slow convergence the method can still not meet the high speed requirements of interactive soft body animation in real time.
Hence, further efforts aimed at finding innovative methods for real time, interactive animation of soft bodies are warranted. In particular, there is a need for fast methods that are sufficiently accurate to produce animations that are realistic enough for a wide range of applications. Further, there is a need for methods that are simple to implement on parallel computing architectures. Still further, there is a need for methods that are easily scalable and/or provide stable solutions.